
//3548.等和矩阵分割II
class Solution {
    //将数组旋转90°
    vector<vector<int>> rotate(vector<vector<int>>& nums)  
    {
        int m=nums.size(),n=nums[0].size();
        vector<vector<int>> ret;
        for(int i=0;i<n;i++)
        {
            vector<int> tmp;
            for(int j=0;j<m;j++)
            tmp.push_back(nums[j][i]);

            ret.push_back(tmp);
        }
        return ret;
    }

public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        long long all=0;
        for(auto& s:grid)
        for(auto e:s) all+=e;

        //写一个删除上半边的逻辑
        auto check=[&](vector<vector<int>> nums)
        {
            auto behave=[&]()
            {
                int m=nums.size(),n=nums[0].size();
                unordered_set<long long> st;
                st.insert({0,nums[0][0],nums[0][n-1]});

                long long up=0;
                for(int i=0;i<m-1;i++)
                {
                    for(auto& e:nums[i]) up+=e;
                    long long low=all-up;

                    if(st.count(up-low)) return true;
                    if(i!=0)
                    {
                        for(int j=0;j<n;j++)
                        if(up-low==nums[i][j]) return true;  //删除分割线处元素看能否满足条件
                        else if(n!=1) st.insert(nums[i][j]);   //将可以被删除的元素存储起来
                    }
                    else 
                        for(auto e:nums[0]) st.insert(e);  //第一行，边界情况
                }
                return false;
            };

            if(behave()) return true;
            //将数组上下颠倒
            reverse(nums.begin(),nums.end());
            if(behave()) return true;

            return false;
        };
        return check(grid)||check(rotate(grid));
    }
};